package zuo.algo.c20;

/**
 * 给定一个非负整数n，代表二叉树的节点个数。返回能形成多少种不同的二叉树结构
 */
public class A06 {

    /**
     * n 0 1 2
     * r 1 1 2
     */
    public static int exc1(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 0 || n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            int left = exc1(i);
            int right = exc1(n - 1 -i);
            res += left + right;
        }
        return res;
    }

    public static int exc2(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 0 || n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = 0;
        }
        return exc2(n, dp);
    }

    private static int exc2(int n, int[] dp) {
        int res = dp[n];
        if (res != 0) {
            return res;
        }
        for (int i = 0; i < n; i++) {
            int left = exc2(i);
            int right = exc2(n - 1 -i);
            res += left + right;
        }
        dp[n] = res;
        return res;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 1000000; i++) {
            int res1 = exc1(i);
            int res2 = exc2(i);
            if (res1 != res2) {
                System.out.println("i = " + i + " res1 = " + res1 + " res2 = " + res2);
                throw new RuntimeException();
            }
            System.out.println(i);
        }
    }
}
